#include <iostream>
#include <type_traits>

// 定义一个基本的类型列表节点
template<int H, typename T = void>
struct Typelist {
    static constexpr int value = H;
    using rest = T;
};

// 类型列表的结束标记
using NullType = void;

// 打印类型列表
template <typename List>
void printTypelist() {
    if constexpr (!std::is_same_v<List, NullType>) {
        std::cout << List::value << " -> ";
        printTypelist<typename List::rest>();
    } else {
        std::cout << "End of List" << std::endl;
    }
}

// 冒泡排序的单次迭代，比较头两个元素，如果需要，则交换它们
template<typename List>
struct BubbleSortStep;

// 两个元素以及后续列表
template<int H1, int H2, typename Rest>
struct BubbleSortStep<Typelist<H1, Typelist<H2, Rest>>> {
    using type = std::conditional_t<
        (H1 <= H2),
        Typelist<H1, typename BubbleSortStep<Typelist<H2, Rest>>::type>,
        Typelist<H2, typename BubbleSortStep<Typelist<H1, Rest>>::type>
    >;
};

// 只有一个元素或没有元素时的处理
template<int H>
struct BubbleSortStep<Typelist<H, NullType>> {
    using type = Typelist<H, NullType>;
};

template<>
struct BubbleSortStep<NullType> {
    using type = NullType;
};

// 冒泡排序的完整逻辑，持续应用BubbleSortStep，直到列表完全排序
template<typename List, unsigned N>
struct BubbleSort {
    using sorted_tail = typename BubbleSort<typename BubbleSortStep<List>::type, N-1>::type;
    using type = typename BubbleSortStep<sorted_tail>::type;
};

template<typename List>
struct BubbleSort<List, 1> {
    using type = List;
};

template<typename List>
struct BubbleSort<List, 0> {
    using type = List;
};

int main() {
    std::cout << "Sorted types: ";
    printTypelist<BubbleSort<Typelist<3, Typelist<1, Typelist<2, Typelist<8, Typelist<5, Typelist<4, NullType>>>>>>, 6>::type>();
    return 0;
}